import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[]array={1,9,2,8,3,7,4,6,5};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left>right){
            return;
        }
        int pivot = partition(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    private static int partition(int[] array, int left, int right) {
        int i = left;
        int key = array[left];
        while(left<right){
            while(left<right&&array[right]>=key){
                right--;
            }
            while(left<right&&array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }

    private static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}
